import java.util.Arrays;
import java.util.Locale;

/**
 * Created by L.jp
 * Description:有一种将字母编码成数字的方式：'a'->1, 'b->2', ... , 'z->26'。
 * 我们把一个字符串编码成一串数字，再考虑逆向编译成字符串。
 * 由于没有分隔符，数字编码成字母可能有多种编译结果，例如 11 既可以看做是两个 'a' 也可以看做是一个 'k' 。但 10 只可能是 'j' ，因为 0 不能编译成任何结果。
 * 现在给一串数字，返回有多少种可能的译码结果
 * User: 86189
 * Date: 2022-08-30
 * Time: 23:48
 */
public class Solution {
    public int solve (String nums) {
        //使用dp数组表示前i个字母的译码方法有多少种
        //如果是单个译码，那么只有一种方法，dp[i]=dp[i-1],如果是组合译码，只要前一个不是0，
        // 那么就有dp[i]=dp[i-1]+dp[i-2]种
        if(nums.equals("0")){
            return 0;
        }
        if(nums.equals("10") || nums.equals("20")){
            return 1;
        }
        for(int i=1;i<nums.length();i++){
            //当0的前⾯不是1或2时，⽆法译码，0种
            //译码总数看整体，如果有0且前面的一个数不是1或者2，那么就完成不了译码
            if(nums.charAt(i)=='0'){
                if(nums.charAt(i-1)!='1' && nums.charAt(i-1)!='2' ){
                    return 0;
                }
            }
        }
        int[] dp = new int[nums.length() + 1];
        //辅助数组初始化为1
        Arrays.fill(dp, 1);
        for(int i = 2; i <= nums.length(); i++){
            //在11-19，21-26之间的情况
            if((nums.charAt(i - 2) == '1' && nums.charAt(i - 1) !=
                    '0') || (nums.charAt(i - 2) == '2' && nums.charAt(i - 1) > '0' &&
                    nums.charAt(i - 1) < '7'))
                dp[i] = dp[i - 1] + dp[i - 2];
            else
                dp[i] = dp[i - 1];
        }
        return dp[nums.length()];
    }
}
